import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

class LinkedListNode<T extends Comparable<T>> {
    T data;
    LinkedListNode<T> next;

    LinkedListNode(T data) {
        this.data = data;
    }

    LinkedListNode(T data, LinkedListNode<T> next) {
        this.data = data;
        this.next = next;
    }

    public LinkedListNode() {
        this.data = null;
    }

    @Override
    public String toString() {
        return "LinkedListNode{" +
                "data=" + data +
                '}';
    }
}

public class LinkedLists {
    public static void main(String[] args) {
        LinkedList<Integer> intList = new LinkedList<Integer>(1, 4, 2, 5, 7, 1, 6, 3, 8, 3, 1, 14, 3, 2, 9, 8, 4);
        System.out.println("The list we have:   " + intList);
        int k = 5;
        LinkedListNode<Integer> kthElementFromEnd = intList.getKthElemntFromTheEnd(k);
        System.out.println("Let's find the k-th element from the end: " + kthElementFromEnd.data);
        intList.removeNode(kthElementFromEnd);
        System.out.println("Remove k-th element " + intList);
        int pivotValue = 3;
        System.out.println("Partition around " + pivotValue + ": " + intList.partitionListAround(pivotValue));
        intList.removeDuplicates();
        System.out.println("Duplicates removed: " + intList);
        LinkedList<Integer> list239 = new LinkedList<Integer>(9, 3, 2);
        LinkedList<Integer> list511 = new LinkedList<Integer>(1, 6, 5);
        System.out.println(list239 + "  +   " + list511 + "   =   " + LinkedList.sumUp(list239, list511));
        LinkedList<Integer> palindrome = new LinkedList<Integer>(1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1);
        LinkedList<Integer> notPalindrome = new LinkedList<Integer>(1, 2, 3, 4, 5, 6, 7, 6, 5, 2, 3, 2, 1);
        System.out.println("Is this [" + palindrome + "] a palindrome? -- " + palindrome.isPalingrome());
        System.out.println("Is this [" + notPalindrome + "] a palindrome? -- " + notPalindrome.isPalingrome());

    }

    static class LinkedList<T extends Comparable<T>> {
        LinkedListNode<T> head;

        LinkedList(LinkedListNode<T> head) {
            this.head = head;
        }

        public LinkedList(T... values) {
            LinkedListNode<T> tail = null;
            for (T value : values) {
                if (head == null) {
                    head = new LinkedListNode<T>(value);
                    tail = head;
                } else {
                    tail.next = new LinkedListNode<T>(value);
                    tail = tail.next;
                }
            }
        }

        /*
            2.5 You have two numbers represented by a linked list, where each node contains a
            single digit. The digits are stored in reverse order, such that the Ts digit is at the
            head of the list. Write a function that adds the two numbers and returns the sum
            as a linked list.
            EXAMPLE
            Input: (7-> 1 -> 6) + (5 -> 9 -> 2).That is, 617 + 295.
            Output: 2 -> 1 -> 9.That is, 912.
            FOLLOW UP
            Suppose the digits are stored in forward order. Repeat the above problem.
            EXAMPLE
            Input: (6 -> 1 -> 7) + (2 -> 9 -> 5).That is, 617 + 295.
            Output: 9 -> 1 -> 2.That is, 912.
         */
        public static LinkedList<Integer> sumUp(LinkedList<Integer> list1, LinkedList<Integer> list2) {
            int value1 = getIntvalue(list1);
            int value2 = getIntvalue(list2);
            int result = value1 + value2;
            return buildIntegersList(result);
        }

        private static int getIntvalue(LinkedList<Integer> list) {
            if (list == null) return 0;
            int result = 0;
            int power = 1;
            LinkedListNode<Integer> currentNode = list.head;
            while (currentNode != null) {
                result += power * currentNode.data;
                power *= 10;
                currentNode = currentNode.next;
            }
            return result;
        }

        private static LinkedList<Integer> buildIntegersList(int result) {
            LinkedList<Integer> list = new LinkedList<Integer>();
            LinkedListNode<Integer> current = list.head;
            while (result > 0) {
                list.insert(new LinkedListNode<Integer>(result % 10));
                result /= 10;
            }
            return list;
        }

        /*
            2.1 Write code to remove duplicates from an unsorted linked list.
            FOLLOW UP   How would you solve this problem if a temporary buffer is not allowed?
        */
        public void removeDuplicates() {
            Set<T> visitedNodes = new HashSet<T>();
            LinkedListNode<T> current = this.head;
            LinkedListNode<T> prev = null;
            while (current != null) {
                if (visitedNodes.contains(current.data)) {
                    if (prev != null) {
                        prev.next = current.next;
                    }
                } else {
                    visitedNodes.add(current.data);
                    prev = current;
                }
                current = current.next;
            }
        }

        /*
            2.2 Implement an algorithm to find the kth to last element of a singly linked list.
        */
        public LinkedListNode<T> getKthElemntFromTheEnd(int k) {
            LinkedListNode<T> result = this.head;
            LinkedListNode<T> current = this.head;
            int stepsCounter = 0;
            while (current != null && stepsCounter < k) {
                current = current.next;
                stepsCounter++;
            }
            if (stepsCounter < k) return null;
            while (current != null) {
                result = result.next;
                current = current.next;
            }
            if (stepsCounter == k) return result;
            return null;
        }

        @Override
        public String toString() {
            StringBuilder result = new StringBuilder();
            LinkedListNode<T> current = head;
            while (current != null) {
                result.append(current.data);
                result.append("--> ");
                current = current.next;
            }
            result.append("NULL");
            return result.toString();
        }

        /*
             2.3 Implement an algorithm to delete a node in the middle of a singly linked list,  given only access to that node.
            EXAMPLE
            Input: the node c from the linked list a->b->c->d->e
            Result: nothing is returned, but the new linked list looks like a- >b- >d->e
        */
        public void removeNode(LinkedListNode<T> node) {
            LinkedListNode<T> current = this.head;
            while (current != null) {
                if (current.next != null) {
                    if (current.next == node) {
                        current.next = current.next.next;
                        return;
                    }
                }
                current = current.next;
            }
        }

        /*
           2.4 Write code to partition a linked list around a value x, such that all nodes less than
           x come before all nodes greater than or equal to x.
       */
        public LinkedList<T> partitionListAround(T value) {
            LinkedList<T> leftPartList = new LinkedList<T>();
            LinkedList<T> rightPartList = new LinkedList<T>();
            LinkedListNode<T> current = head;
            int sameValueCounter = 0;
            while (current != null) {
                if (current.data == null || current.data.compareTo(value) < 0) {
                    leftPartList.insert(current);
                } else {
                    if (current.data.compareTo(value) == 0) {
                        sameValueCounter++;
                    } else {
                        rightPartList.insert(current);
                    }
                }
                current = current.next;
            }
            for (int i = 0; i < sameValueCounter; i++) {
                leftPartList.insert(new LinkedListNode<T>(value));
            }

            return mergeTwoLists(leftPartList, rightPartList);
        }

        public LinkedList<T> mergeTwoLists(LinkedList<T> list1, LinkedList<T> list2) {
            LinkedListNode<T> current = list1.head;
            if (current == null) return new LinkedList<T>(list2 == null ? null : list2.head);
            while (current.next != null) current = current.next;
            current.next = list2.head;
            return new LinkedList<T>(list1.head);
        }

        private void insert(LinkedListNode<T> node) {
            if (node == null) return;
            LinkedListNode<T> current;
            if (head != null) {
                current = head;
                while (current.next != null) {
                    current = current.next;
                }
                current.next = new LinkedListNode<T>(node.data);
            } else {
                head = new LinkedListNode<T>(node.data);
            }

        }

        /*
            Given a circular linked list, implement an algorithm which returns the node at  the beginning of the loop.
            DEFINITION
            Circular linked list: A (corrupt) linked list in which a node's next pointer points
            to an earlier node, so as to make a loop in the linked list.
            EXAMPLE
            Input: A - > B - > C - > D - > E - > C [the same C as earlier]
            Output: C
        */
        public LinkedListNode<T> getCycleStartPoint() {
            if (this.head == null) return null;
            LinkedListNode<T> slowRunner = this.head;
            LinkedListNode<T> fastRunner = this.head;
            while (fastRunner.next != null && fastRunner.next.next != null) {
                slowRunner = slowRunner.next;
                fastRunner = fastRunner.next.next;
                if (slowRunner == fastRunner) break;
            }
            if (slowRunner != fastRunner) {
                return null; // No cycle was found
            }

            slowRunner = this.head;
            while (slowRunner != fastRunner) {
                slowRunner = slowRunner.next;
                fastRunner = fastRunner.next;
            }
            return slowRunner;
        }

        /*
         2.7 Implement a function to check if a linked list is a palindrome.
      */
        public boolean isPalingrome() {
            if (this.head == null) return true;
            if (this.head.next == null) return true;
            Stack<T> stack = new Stack<T>();
            LinkedListNode<T> slow = head;
            LinkedListNode<T> fast = head.next;
            stack.push(this.head.data);
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                stack.push(slow.data);
            }
            if (fast.next != null) { // odd length case
                slow = slow.next;
            }
            while (slow.next != null) {
                slow = slow.next;
                T valueFromStack = stack.pop();
                if (valueFromStack.compareTo(slow.data) != 0) {
                    return false;
                }
            }
            return true;
        }
    }
}
